package oct2013.linkednode;

/**
 * @author Yinzi Chen
 * @date Nov 13, 2013
 */
public class InsertionSortList {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode cur, prev;
        while (head != null) {
            cur = dummy.next;
            prev = dummy;
            while (cur != null && cur.val <= head.val) {
                prev = cur;
                cur = cur.next;
            }
            prev.next = head;
            head = head.next;
            prev.next.next = cur;
        }
        return dummy.next;
    }
}
